package org.basis.algorithm.promote;

import lombok.Data;

/**
 * 链表反向
 *
 * @author Mr_wenpan@163.com 2022/02/22 16:15
 */
public class ListReverse {

    public static void main(String[] args) {
        Node node1 = new Node("1");
        Node node2 = new Node("2");
        Node node3 = new Node("3");
        Node node4 = new Node("4");
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        printReverseList(node1);

    }


    /**
     * 不使用额外空间逆序打印链表
     */
    public static void printReverseList(Node node) {
        if (node == null) {
            return;
        }

        process(node);
    }

    /**
     * 使用递归逆序打印链表
     */
    public static void process(Node node) {
        if (node == null) {
            return;
        }
        process(node.next);
        System.out.println(node.value);
    }

    @Data
    static class Node {
        private Node next;
        private String value;

        public Node(String value) {
            this.value = value;
        }
    }

    public static void printReverseList2(Node node) {
        if (node == null) {
            return;
        }
        if (node.next == null) {
            System.out.println(node.value);
            return;
        }
        // 先反转链表
        Node cur = node;
        Node pre = null;
        Node next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        // 此时pre为反转后的头节点
        while (pre != null) {
            System.out.println(pre.value);
            pre = pre.next;
        }
    }

}
